package mess;

import javax.swing.tree.TreeNode;

public class LeeCode_108 {
    public static void main(String[] args) {
        sortedArrayToBST(new int[]{-10, -3, 0, 5, 9});
        //sortedArrayToBST(new int[]{3,5,8});
        //sortedArrayToBST(new int[]{0});
    }

    private static TreeNode sortedArrayToBST(int[] nums) {
        int len = nums.length;
        TreeNode root = new TreeNode();
        backTrick(nums, 0, len - 1, root);
        return root;
    }

    private static void backTrick(int[] nums, int l, int r, TreeNode node) {
        int mid = l + (r - l) / 2;
        node.val = nums[mid];
        if (mid == l) {
            if (l == r)
                return;
            node.right = new TreeNode(nums[r]);
            return;
        }
        node.left = new TreeNode();
        node.right = new TreeNode();
        backTrick(nums, l, mid - 1, node.left);
        backTrick(nums, mid + 1, r, node.right);
    }

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
